Author Topic: интересная задачка, кротчайший путь через кучу точек.  (Read 4606 times)

0 Members and 1 Guest are viewing this topic.

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
есть поле, на котором 15 красных точек. разбросаны рандомно. на поле появляется 16-я точка, зеленая, также в рандомном месте.



требуется начиная с зеленой точки пройти через все красные точки. но так, чтобы  сумма всех отрезков пути была минимальна. тоесть нужно определить наименьший маршрут через все точки. на практике это будет выглядеть следующим образом: зеленая точка движется к нужной, заранее определенной как более выгодной, красной точке. эта красная точка исчезает. идем дальше.

сейчас действует система нахождения близ лежащей красной точки. такая система работает неплохо, но судя по картинке, приведенной в примере, зеленая точка пойдет в начале влево и верх, а после этого только вернется за двумя точками справа с низу, что не очень выгодно.


dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
нет, это не существенно. после прохождение всех точек, можно двигаться очень быстро, так-что положение последней точки не играет роль.

Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
« Last Edit: May 13, 2016, 05:35:11 PM by Vint »


Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
А, не. Задача коммивояжера...

Quote
Это НП-полная задача, т.е. нет полиноминального алгоритма для ее решения. (В теории алгоритмов NP-полные задачи — это класс задач, лежащих в классе NP (то есть для которых пока не найдено быстрых алгоритмов решения, но проверка того, является ли данное решение правильным, проходит быстро), к которым сводятся все задачи класса NP. Это означает, что если найдут быстрый алгоритм для решения любой из NP-полных задач, любая задача из класса NP может быть решена быстро.) То есть за O(N^2) при задачу решить невозможно. Только за O(N!). А это значит, что даже для ста точек компьютер не успеет рассчитать маршрут (за реальное время, конечно же).

Значит нужно решить приближенно.

Короче, зависит от количества точек. Сложность прямого перебора N!


dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
почемуто мне сразу пришла мысль просчитать все возможные пути, и найти среди них самый короткий :-\ . но пока нет времени заморочиться этим, вот и написал на форум. неуверен насчет скорости.

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
Алгоритм Дейкстры

ru.wikipedia.org/wiki/Алгоритм_Дейкстры

https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
только сейчас посмотрел что за алгоритм.
так по этому принципу у меня сейчас и работает.
Quote
сейчас действует система нахождения близ лежащей красной точки. такая система работает неплохо, но судя по картинке, приведенной в примере, зеленая точка пойдет в начале влево и верх, а после этого только вернется за двумя точками справа с низу, что не очень выгодно.
определяю расстояние до всех точек, нахожу наименьшее, и иду к ней. потом с нового места ищу ближайшую точку, и т.д.

Кликермен

  • Активный участник
  • ***
  • Posts: 112
    • View Profile
определяю расстояние до всех точек, нахожу наименьшее, и иду к ней. потом с нового места ищу ближайшую точку, и т.д.
mак не выгодно,  воm карmuнка, а перебором очень долго..

А есmь код? u как называеmся uгра?

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
код который работает примерно такой,
Code: (clickermann) [Select]
UNDEFINE($trees_arr)
GETSCREEN

IF_PIXEL_IN(0,0, $_xmax,$_ymax, 16739583)
   $x_pl = $_return1
   $y_pl = $_return2
END_IF   //находим нахождение "зеленой точки"

SCANPXL($trees_arr, $x_pl-200,$y_pl-200,$x_pl+200,$y_pl+200, 255) //нашли все точки красные, их намного больше чем 15, так как метки большие, и разные, это скапления цвета 255



WHILE(ARRSIZE($trees_arr))
   
   $min_dist = DIST($x_pl,$y_pl,$trees_arr[0],$trees_arr[1])
   $near_tree_x = $trees_arr[0]
   $near_tree_y = $trees_arr[1]
   FOR($i=2,$i<ARRSIZE($trees_arr),2)
     
      $temp_dist = DIST($x_pl,$y_pl,$trees_arr[$i],$trees_arr[$i+1])
     
      IF($temp_dist < $min_dist)
         $min_dist = $temp_dist
         $near_tree_x = $trees_arr[$i]
         $near_tree_y = $trees_arr[$i+1]
      END_IF
   END_CYC
   //нашли точку которая на минимальном расстоянии
   
   //тут двигаемся к красной точке по координатам  $near_tree_x $near_tree_у
   //делаем действия, она пропадает
   //и дальше пока не пропадут все красные метки.

   GETSCREEN($x_pl-200,$y_pl-200,$x_pl+200,$y_pl+200)
   IF_PIXEL_IN($x_pl-200,$y_pl-200,$x_pl+200,$y_pl+200, 16739583)
      $x_pl = $_return1
      $y_pl = $_return2
   END_IF

   
   UNDEFINE($trees_arr)
   SCANPXL($trees_arr, $x_pl-200,$y_pl-200,$x_pl+200,$y_pl+200, 255)
   
END_CYC
не относится к рисунку в примере. убрал лишнее.

и да, все верно, часто маршрут выходит уж очень не выгодный. часто собирает точки в одном направлении, и в конце возвращается за точкой в начало, вместо того чтобы взять одну точку которая хоть и дальше немного, но потом чтоб за ней не возвращаться.

Vint

  • Супермодератор
  • Герой форума
  • *
  • Posts: 3935
  • Лечу куда хочу. cman 4.13.014x32, 4.14.003 W10
    • View Profile
Предлагаю учесть самую дальнюю точку и выбирать точки в противоположном направлении.
Вот в примере дальняя точка примерно слева вверху, значит обходим по ближайшим, но учитываем сначала справа снизу, пока такие точки не закончатся. Потом как и раньше.
Это не решит всех проблем, но отдельную кучку точек не 'забудет'.


dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
какбы это все не настолько важно, все итак неплохо работает. просто хотел оживить настроение, так сказать поднапреч мысли.  :D . будет время, попробую насчет перебора всех возможных вариантов, ради интереса. просто думал может кто присоиденится :D

Кликермен

  • Активный участник
  • ***
  • Posts: 112
    • View Profile
какбы это все не настолько важно, все итак неплохо работает. просто хотел оживить настроение, так сказать поднапреч мысли.  :D . будет время, попробую насчет перебора всех возможных вариантов, ради интереса. просто думал может кто присоиденится :D
диплом напишу, помогу)  а есть ссылка на эту игру? гугл ничего не дает)

dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
будет время, попробую насчет перебора всех возможных вариантов, ради интереса. просто думал может кто присоединится :D
И вот оно, врема  ;D . Не прошло и 2 года...

Так вот, вариант с перебором всех возможных вариантов прохождения маршрута.
Весь упор был именно в создания "списка" этих всех вариантов. Сегодня не мало почитал литературы, просмотрел кучи кода, но так и не понял всю суть генерации этих самых "перестановок" элементов массива.

Пришлось стырить код вот отсюда https://prog-cpp.ru/permutation/ . Там кстати более менее доходчиво описан алгоритм перестановок.

Переписал код на кликерман. Немного подрихтавал. Он заработал, но как он работает, ХЗ  :-\. Если ктонибудь понимает чтото в этом, обьясните пожалуйста  ::) .

Код на данном выше рисунке не тестил. Писал код, чтобы проверить насколько он быстро будет считать. Как оказалось, до шести точек скорость приемлема. Если добавить седьмую, то время выполнения уже повышается до 13-14 секунд. Восемь точек - почти две минуты :o .

Code: (text) [Select]
18:28:07 стартуем, количество точек - 5
18:28:08 минимальное расстояние - 309.67098701672
18:28:08 через точки 0_8_2_6_4
18:28:08 время выполнения - 0.273сек.
18:28:08 
18:28:15 стартуем, количество точек - 6
18:28:17 минимальное расстояние - 314.37419984377
18:28:17 через точки 0_8_2_6_10_4
18:28:17 время выполнения - 1.795сек.
18:28:17 
18:28:30 стартуем, количество точек - 7
18:28:44 минимальное расстояние - 351.57401372562
18:28:44 через точки 0_8_2_12_6_10_4
18:28:44 время выполнения - 13.584сек.
18:28:44 
18:29:12 стартуем, количество точек - 8
18:31:12 минимальное расстояние - 509.4178762202
18:31:12 через точки 2_12_6_10_4_8_0_14
18:31:12 время выполнения - 118.953сек.
18:31:12 

Дальше не тестил  :D

Code: (clickermann) [Select]
SUB(next, $n)   //генератор перестановок, вернет  $check = 1 если закончатся варианты
   
   $check = 0
   $j = $n - 2
   WHILE((($j != -1) & ($i_arr[$j] >= $i_arr[$j+1])) ^ $check = 1)
      $j = $j-1
      IF($j = -1)
         //   print("вариантов больше нет")
         $j = 0
         $check = 1
      END_IF
   END_CYC
   
   IF($check = 0)
      $k = $n -1
      WHILE($i_arr[$j] >= $i_arr[$k])
         $k = $k - 1
      END_CYC
     
      $s = $i_arr[$j]
      $i_arr[$j] = $i_arr[$k]
      $i_arr[$k] = $s
     
      $l = $j + 1
      $r = $n - 1
      WHILE($l < $r)
         $s = $i_arr[$l]
         $i_arr[$l] = $i_arr[$r]
         $i_arr[$r] = $s
         $l = $l + 1
         $r = $r - 1
      END_CYC
   END_IF
   
END_SUB
//.............................................................................

//начальные данные

$x_start = 70
$y_start = 120

$ch_point[0] = 50
$ch_point[1] = 150
$ch_point[2] = 130
$ch_point[3] = 90
$ch_point[4] = 110
$ch_point[5] = 20
$ch_point[6] = 180
$ch_point[7] = 50
$ch_point[8] = 40
$ch_point[9] = 110
$ch_point[10] = 130
$ch_point[11] = 16
//$ch_point[12] = 190
//$ch_point[13] = 90
//$ch_point[14] = 18
//$ch_point[15] = 250
//$ch_point[16] = 8
//$ch_point[17] = 6
//$ch_point[18] = 21
//$ch_point[19] = 24

FOR($ind=0,$ind < ARRSIZE($ch_point),2)
   arrpush($i_arr, $ind)
END_CYC



// поиск минимального маршрута через точки.
print("стартуем, количество точек - ",ARRSIZE($i_arr))
$t = $_ms
WHILE($check = 0)
   
   $dots =$i_arr[0]
   FOR($ind=1,$ind<ARRSIZE($i_arr))
      $dots = STRCONCAT($dots,"_",$i_arr[$ind])
   END_CYC
   //  print("маршрут через точки ", $dots)
   
   $dist = dist($x_start,$y_start,$ch_point[$i_arr[0]],$ch_point[$i_arr[0]+1])
   
   FOR($ind=0,$ind<ARRSIZE($i_arr)-1)
      $dist = $dist + dist($ch_point[$i_arr[$ind]],$ch_point[$i_arr[$ind]+1],$ch_point[$i_arr[$ind+1]],$ch_point[$i_arr[$ind+1]+1])
   END_CYC
   //  print("дистанция = ", $dist)
   
   DEFINE($min, $dist)
   DEFINE($track, $dots)
   IF($dist < $min)
      $min = $dist
      $track =  $dots
   END_IF
   
   next(ARRSIZE($i_arr))
END_CYC

print("минимальное расстояние - ", $min)
print("через точки ", $track)
print("время выполнения - ", ROUND(($_ms-$t)/1000,-3),"сек.")
print(" ")

halt
Генератор перестановок возможно комунибудь пригодится. Работает кок положено, вот что он делает с числами к примеру - 1234
Code: (text) [Select]
18:41:51 1_2_3_4
18:41:51 1_2_4_3
18:41:51 1_3_2_4
18:41:51 1_3_4_2
18:41:51 1_4_2_3
18:41:51 1_4_3_2
18:41:51 2_1_3_4
18:41:51 2_1_4_3
18:41:51 2_3_1_4
18:41:51 2_3_4_1
18:41:51 2_4_1_3
18:41:51 2_4_3_1
18:41:51 3_1_2_4
18:41:51 3_1_4_2
18:41:51 3_2_1_4
18:41:51 3_2_4_1
18:41:51 3_4_1_2
18:41:51 3_4_2_1
18:41:51 4_1_2_3
18:41:51 4_1_3_2
18:41:51 4_2_1_3
18:41:51 4_2_3_1
18:41:51 4_3_1_2
18:41:51 4_3_2_1

Так выглядят восемь точек что у меня в коде, и минимальный маршрут, красная линия это старт:





dramster

  • Герой форума
  • *****
  • Posts: 1134
    • View Profile
https://ru.wikipedia.org/wiki/Задача_коммивояжёра#Метод_ветвей_и_границ

Это ж когда-то Vint об этом писал еще, но тогда я как-то даже и не обратил внимание и не глянул что это такое.

А, не. Задача коммивояжера...
...
Короче, зависит от количества точек. Сложность прямого перебора N!



Интересно, как этот "метод ветвей и границ" работает  ::).
Quote
Методы дискретной оптимизации, в частности ветвей и границ, позволяют находить оптимальные или приблизительные решения для достаточно больших задач.



Немного почитал, и у меня появились сомнения, что это немного не то  ??? . Задача то у  Коммивояжера была какая - проехать все города и вернуться обратно. Соответственно - метод ветвей и границ также строит маршрут через все города с возвратом в начало, то есть по кругу. Более менее понятно описан алгоритм тут http://galyautdinov.ru/post/zadacha-kommivoyazhera . Вроде не сложно, возможно гдето применимо, но в этой теме задача немного другая была - тупо спилить все деревья на поляне, при этом пробежать наименьший маршрут  :D. Если с городами, то стартануть с определенного города и посетить все остальные, при этом неважно где мы финишируем (назад летим самолетом).
« Last Edit: September 10, 2018, 03:46:08 PM by dramster »