Графы. Помогите составить смежную матрицу.

[tristram]

Графы. Помогите составить смежную матрицу.

Есть такая вот приблуда:

В функцию поступают два числа от 1 до 1000, она должна вернуть кратчайший путь от вершины a до вершины b., т.е. например 1, 17 = 2. По идее надо матрицу смежности составить с помощью алгоритма Флойда, но я не знаю как это делается. Подскажите плиз, очень нужно.

 

[StUV]

вообще говоря, погугли на "поиск в ширину"
в каком виде у тебя хранится инфо о вершинах ?

зы: перекиньте кто-нибудь тему в офф

 

[tristram]

никогда не хранится. это задачка такая, картинка прилогалась. в итоге получается программа-клиент которая принимает запрос от сервера и должна сгенерировать ответ. но это оффтопик. все готово кроме функции distance().

 

[StUV]

программа клиент для получения результата парсит картинку ?

 

[tristram]

нет. картинка как пример дана просто в задаче. клиент получает в int a и int b. Но это не суть. Суть вопроса в том как реализовать function distance($a,$b)

 

[kvf77]

Погляди здесь:
Очень хорошая ссылка по алгоритмам:
http://alglib.sources.ru/

Другие ссылки:
http://doors.infor.ru/allsrs/alg/index.html
http://en.edu.ru/db/msg/26708/_sp/1407/3220

 

[tristram]

не нашел того что нужно

 

[rotoZOOM]

первое (и самое сложное) что тебе нужно - это преобразовать данные "соты" в прямоугольную таблицу, другими словами назначить каждой "соте" декартовы координаты (x,y). После того, как ты это сделаешь посчитать минимальное расстояние раз плюнуть, оно будет равно:
|xs-xd|+|ys-yd|, где (xd,yd) - это декартовы координаты конечной клетки, а (xs,ys) - соответственно начальной.
Теперь основная задача - это генерация данного поля в декартовой системе.
Присмотримся внимательнее к рисунку и поймем, что мы можем взять ось OX идущую вдоль сот 1,6,17,34,57 и т.д.
ось OY - 1, 4,13,28,49 ...причем в координатах (0,0) будет стоять цифра 1.
Тогда цифре 2 соответствует координаты (0,-1), для 3 (-1,0), для 4 (-1,-1), для 5 (0,1) для 6 (1,0), для 7 (1,-1) и т.д.
Нарисуй это в прямоугольной таблице ты получишь примерно следующее:

4 5
3 1 6
  2 7
  9 8

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

 

[StUV]

tristram

Но это не суть. Суть вопроса в том как реализовать function distance($a,$b)

суть в том, что для реализации
> function distance($a,$b)
необходимо знать с каким представлением данных (представленных тобой только картинкой) будет работать эта функция

для решения задачи достаточно представить твою картинку в виде связного графа и воспользоваться алгоритмом "поиск в ширину", реализаций которого в и-нете до [...]

тебе непонятно как сформировать граф из этой картинки ?

 

[rotoZOOM]

StUV Поиск в ширину в этой задаче не нужен, не путайте клиента.

 

[StUV]

rotoZOOM
=)
если

1,6,17,34,57 и т.д.
ось OY - 1, 4,13,28,49 ...

то почему 2 и 5 лежат на оси Y ?

есть один момент:
осей может быть и 3, так как неясно [1,5] = 2 или 1 ?
т.е. - сколько "прозрачных" граней имеет каждая клетка - если 4 - тогда твой геометрический подход верен, а если 6 граней ?

 

[tristram]

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

-~{}~ 19.08.05 13:33:

какой я ууумныйй... я прям сам балдею весь. итс ворк

 

[rotoZOOM]

StUV объясняю, ось ОX направлена по диагонали снизу-слева вверх-вправо, ось OY направлена строго вверх, они не имеют угол 90 градусов (это нам и не надо).
Именно поэтому номера 66,41,22,9,2,1,5,15,31,53 лежат на оси OY, причем все, которые до 1 имеют отрицательную координату Y.
Центр координат проходит через соту 1.
Такая система координат идентифицирует каждую соту уникально.
Например сота 64 имеет координаты: (2,-5)
А в координатах (3,1) лежит число 56

 

[StUV]

rotoZOOM
[...]
врубился
ну и объясняешь же ты =)))

 

[rotoZOOM]

координаты 1 (0,0), координаты 5 (0,1), значит расстояние равно |0-0|+|0-1|=1

 

[StUV]

опять сорри - не все так просто:
чему в рамках одной системы координат равны расстояния
1 - 16
1 - 7
?

-~{}~ 19.08.05 15:26:

короче - все оч просто:
на рисунке каждая вершина соединена с 6-ю соседними связью с длиной 1 (кроме крайних вершин)
какую бы ты криволинейную систему координат с двумя осями на плоскомти ни выбирал - формула |xs-xd|+|ys-yd| будет давать одно из возможных расстояний, но не кратчайшее, так как такая система координат _по_определению_ предполагает для каждой вершины 4 соседних, до которых расстояние = 1.

 

[rotoZOOM]

Мда, точнее не одно из расстояний, а неправильное расстоние.
Все верно. Я ошибся с формулой расстояния, но построение матрицы надо делать именно так -> мэпим сотовую систему на декартовую, а далее действительно запускаем волну.
Но идти будем не в 4, а в 6 направлениях:
(-1,0), (-1,-1), (0,1), (1,1), (1,0), (0,-1)

 

[tristram]

а меня плохо работает. не совсем верно координаты считает.rotoZOOM
наверное у меня не получится

 

[rotoZOOM]

tristram какие именно координаты ? перевод в декартову систему?

 

[tristram]

да