Вот такая вот задачка ...

← →
JibSkeart © (2003-10-02 14:54) [0]

нужно найти катчайший путь от точки а до б !

НО !!!

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

ну вообшем пример :))
наше поле

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

(путь задается так
из точки А можно перейти в точку Б из точки Б в точки А и С итд

допустим
1->2
1->5
2->3
2->6
3->4
3->7
5->9
6->5
6->10
7->4
7->8
7->12
9->6
9->10
9->13
10->11
10->15
11->7
11->15
11->12
12->16
13->14
14->15
15->16

если нарисовать наше поле и нарисовать стрелки от точки 1 до 2
1 до 5 итд то можно увидеть более наглядно ,
что то подобие лабиринта ,

у меня есть рабочий вариант ,
но хочется посмотреть и другие решения ,

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

← →
Думкин © (2003-10-02 14:57) [1]

Выпил мало? По русски никак?

← →
JibSkeart © (2003-10-02 14:58) [2]

а точнее что непонятно ,
а то у меня мысли расплывабтся :)))

думаю о том о сем ..

← →
mfender © (2003-10-02 15:00) [3]

А где же А и Б?
Загадка? :))

← →
JibSkeart © (2003-10-02 15:02) [4]

ну вмусле от точки 1 до точки 15
воот ...

← →
Kinda © (2003-10-02 15:04) [5]

А где тут точки-то?

← →
han_malign © (2003-10-02 15:05) [6]

Тут, вчера, как раз о "графах" спрашивали...
(Теория графов и сетей)

← →
Игорь Шевченко © (2003-10-02 15:06) [7]

"Как известно, в Петушках нет пунктов А. Пунктов Ц тем
более нет. Есть одни только пункты Б. Так вот: Папанин, желая
спасти Водопьянова, вышел из пункта Б1 в сторону пункта Б2. В
то же мгновение Водопьянов, желая спасти Папанина, вышел из
пункта Б2 в пункт Б1. Неизвестно почему, оба они оказались в
пункте Б3, отстоящем от пункта Б1 на расстоянии 12-ти
водопьяновских плевков, а от пункта Б2 - на расстоянии 16-ти
плевков Папанина. Если учесть, что Папанин плевал на три метра
семьдесят два сантиметра, а Водопьянов совсем не умел плевать,
-выходил ли Папанин спасать Водопьянова?"

← →
JibSkeart © (2003-10-02 15:08) [8]

под точками подразумеваются ЦИФРЫ (1,2,3...16)

теорию графов тоже можно подкинуть

я уже давно это читал
если можно ссылку кинте ...

← →
JibSkeart © (2003-10-02 15:10) [9]

2Игорь Шевченко ©
Весьма оригинально ,
поверь я тоже посмеялся ...

← →
mfender © (2003-10-02 15:14) [10]

1-5-9-13-14-15

← →
JibSkeart © (2003-10-02 15:16) [11]

2mfender
да это так а слабо программно ???

← →
Mike B. © (2003-10-02 15:16) [12]

Чего это он несет? Почему в Петушках нет ни А, ни Ц, а одни только Б? На кого он, ...., намекает?

← →
mfender © (2003-10-02 15:24) [13]

> JibSkeart © (02.10.03 15:16) [11]
да это так а слабо программно ???

Угу...

← →
JibSkeart © (2003-10-02 15:49) [14]

Что дейсвительно неясно изложил задачу ?

← →
Verg © (2003-10-02 15:58) [15]

http://algolist.manual.ru/maths/graphs/index.php

← →
JibSkeart © (2003-10-02 16:05) [16]

Спасибо
почитаем ...

← →
Igorek © (2003-10-02 16:10) [17]

"А в Потрепаться все треп и треп..."

Тот же волновой алгоритм нахождения кратчайшего пути на графе. Кстати предлагаю пускать две волны - с начала и с конца. Так обычно фронты быстрее сойдуться чем один до конца.
Если относительно графа есть какие либо предположения, то можно соотв. модифицировать алгоритм. Напр. это двумерная карта с островами. Но это уже другая история.
И зачем реализовывать, если можно словами... Хотя реализация тоже нетривиальна.

ну дело в том что у меня есть только данные
такие

1->2
2->3
2->1
3->4
3->7

и так далее ...

думещь испольуя только эти точки можно воспользоватся им ?

Канечна, думаю. Это ж матрица инциденций графа. Но подробно никто тебе не напишет - сам рой теорию графов и волновой алгоритм.

Или нет. Нафиг волновой алгоритм. Сделай так:
простой перебор; запускаешь рекурсивную ф-цию, параметр - начало; помечаешь начало как использованный пункт; потом вызываешь ее саму для всех точек в которые можно попасть из текущей; заносишь также текущую точку в глобальный массив пути; когда попал в конечную точку - дописываешь путь в таблицу путей;
Когда все переберет - найдешь самый короткий путь.
Правда я уверен что сей алгоритм не даст хорошую скорость для больших графов. Но для твоего примера - самый раз.

> JibSkeart © (02.10.03 14:54)
Я все это уже плохо помню но, по-моему, кроме волнового алгоритма, тебе стоит поискать еще алгоритмы Дейкстры, Флойда и их товарища Краскала. Возможно они тебе помогут.

Igorek © (02.10.03 16:24) [19]

в том то и дело что у меня 1050 точек :(((
и именно методом перебора я это сделал ...

Mike B. ©

ладненько взгляну ...

Для нахождения одного кратчайшего пути быстрее всего алгоритмы Дейкстры или Форда-Фалкерсона.
Но если потом вдруг понадобятся альтернативные пути - делай сразу на волновом алгоритме.
Реализация всего 4 цикла. Зато получишь матрицу крадчайших путей со всеми альтернативными маршрутами.

А где примеры можно посмотреть ???

???

какие мысли еще есть ?

Вот такая вот задачка ... Найти похожие ветки