Поиск минимального пути между элементами массива

[Yogrik]

Поиск минимального пути между элементами массива

Есть массив:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 24

Вопрос: Мне нужно найти минемальный путь между 2 элементами массива...
т.е к примеру 1 и 13 получается: 1->2->3->8->13 или
1->6->11->12->13
А как это сделать....?

 

[IntenT]

Yogrik
рекурсией

 

[HEm]

тебе нужно найти путь межд элементами
(a,b) и (c,d)
рассмотрим решение для случая когда a<=c и b<=d (всего таких случаев 3, другие 2:
a<=c, b>=d и a>=c, b<=d, случай a>=c, b>=d легко превращается в первый):

for ($i=a;$i<=c;$i++) {
  for ($j=b;$j<=d;$j++) {
    echo $massiv[$i,$j]."->";
  }
}

В первом приближении примерно так
аналогично для прочих случаев

-~{}~ 03.08.04 19:43:

это если массив не разреженный

 

[Yogrik]

А массив как раз разреженный....

 

[HEm]

у.... тада надо математику в дело пускать, я пас

 

[Yogrik]

На самом деле массив имеет вид:

0 0 0 10 4 29 28 0
0 0 0 23 30 27 50 0
0 18 22 12 20 59 9
0 17 52 51 37 19 21 57
0 15 46 35 33 13 55 0
6 7 14 42 36 1 56 0
48 32 3 11 34 38 0 0
60 58 44 43 24 39 0 0
49 8 2 26 25 40 0 0
53 0 0 45 16 41 0 0
54 0 0 0 4 31 0 0

Соответственно через нули путь проходить не может

 

[Silent]

Видимо нужно брать в руки книгу по теории алгоритмов и читать главу в алгоритмами на графах. Поскольку я с графами никогда не сталкивался, то за пару минут придумалось следущее:

1) заводишь еще один массив такого же размера,
2) начинаешь с конечной точки, во втором массиве помечаешь, что попасть в нее можно за 0 ходов.
3) проверяешь все окружающие точки (их 8) и для непустых запоминаешь, что попасть из них в конечную можно за 1 ход (и там же запоминаешь путь каким-нибудь образом),
4) для всех точек, добавленных во второй массив на предыдущем шаге, проверяешь их окружение и помечаешь, что из них в конечную можно попасть за два хода (запоминаешь, каким именно путем),
4а) если на четвертом шаге окажется, что обрабатываемая точка уже есть во втором массиве, то ее пропускаешь, потому что тебе уже известен путь от нее к конечной точке, и этот путь короче, чем тот, что ты нашел на данном шаге.

Повторяешь шаги 4-4а до тех пор, пока не наткнешься на исходную точку. Наверняка этот алгоритм можно оптимизировать, но это уже другая проблема.

 

[SiMM]

Если не ошибаюсь, то алгоритм надо искать в google.ru по запросу алгоритм решения задачи коммивояжёра (хотя тут вроде нет задачи обойти все элементы массива - но кто знает, чего на самом деле хотел автор?). Конечная реализация на PHP, думаю, труда не составит -> задача к PHP отношения не имеет - она алгоритмическая