Hardprob/Minimum Planar Record Packing — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} --> * Коллекция <em>C</em> из <em>n</em> записей, ** для каждой зап…»)
 
(Массовая правка: замена PCRE <m>(\w)\s*∈\s*(\w)</m> на <em>\1 ∈ \2</em>)
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
<!-- start --><!-- {{svg-image-for-hard-problem|{{PAGENAME}}}} -->
 
* Коллекция <em>C</em> из <em>n</em> записей,  
 
* Коллекция <em>C</em> из <em>n</em> записей,  
** для каждой записи <m>c\in C</m> задана некоторая вероятность <em>p(c)</em>, <m>0\le p(c)\le 1</m>.
+
** для каждой записи <em>c C</em> задана некоторая вероятность <em>p(c)</em>, <m>0≤p(c)≤1</m>.
* Найти для каждой записи из <m>c\in C</m> размещение <em>z(c)</em> на плоскости, заданное целочисленными координатами, так, что все записи расположены на разных точках этой плоскости.
+
* Найти для каждой записи из <em>c C</em> размещение <em>z(c)</em> на плоскости, заданное целочисленными координатами, так, что все записи расположены на разных точках этой плоскости.
 
* Минимизировать  
 
* Минимизировать  
  <m>\displaystyle\sum\limits_{c_1\in C} \displaystyle\sum\limits_{c_2\in C} p(c_1) p(c_2) d(z(c_1),z(c_2)) → \min</m>,  
+
  <m>\displaystyle\sum\limits_{c_1∈  C} \displaystyle\sum\limits_{c_2∈  C} p(c_1) p(c_2) d(z(c_1),z(c_2)) → \min</m>,  
 
где <m>d(z(c_1),z(c_2))</m> — дискретное евклидово расстояние между точками <m>z(c_1)</m> и <m>z(c_2)</m>.
 
где <m>d(z(c_1),z(c_2))</m> — дискретное евклидово расстояние между точками <m>z(c_1)</m> и <m>z(c_2)</m>.
  

Текущая версия на 22:05, 17 апреля 2023

  • Коллекция C из n записей,
    • для каждой записи c ∈ C задана некоторая вероятность p(c), .
  • Найти для каждой записи из c ∈ C размещение z(c) на плоскости, заданное целочисленными координатами, так, что все записи расположены на разных точках этой плоскости.
  • Минимизировать
, 

где — дискретное евклидово расстояние между точками и .


Задача в лаб22 (рид-онли просмотр)