Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Нахождение кратчайшего пути

Автор: samec 13.11.2007 22:53

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

Код
Номер пункта    x    y
    1               2.0    8.0
    2             10.0    9.0
    3               1.0    2.0
    4               4.0    9.0
    5               9.0    5.0


Следует учесть, что в указанном районе есть озеро и проходит железная дорога.
Координаты, ограничивающие местоположение аэродрома и станции, приведены в след. таблице:
Код
Объект            Координата x    Координата y
Озеро                (>=0 и <=4)    (>=3 и <=6)    
Железная дорога        (>=6)        (=1)

Проиллюстрировать графически.
----------------------------------------------------------
Каким способом найти координаты станции и аэродрома???

Автор: Lapp 14.11.2007 9:42

Я правильно понял, что товары привозят по ЖД, потом от станции воздухом до АП, а потом ножками до каждого НП?
Табличка не совсем понятная.. Так, что ли:

Озеро: 0<=x<=4, 3<=y<=6
Железная дорога: 6<=x, y=1

- да?
И нужно минимизировать сумму всех маршрутов?

Автор: samec 14.11.2007 16:55

Да, всё верно, только от аэродрома до населенных пунктом тоже вертолёт летать будет. Таблички подправил.
Да. нужно минимизаровать сумму всех маршрутов.

Автор: Lapp 14.11.2007 17:09

Ну, я бы начал с того, что нарисовал это все. Оно, может, и не совсем правильно - зато хоть как-то оживит процесс. Тем более, что графика все равно нужна smile.gif.
Выбираешь масштаб, наносишь все объекты, подписываешь.. А там видно будет smile.gif))

Автор: samec 14.11.2007 17:51

я на бумажке нарисовал smile.gif

Автор: Lapp 14.11.2007 18:09

Цитата(samec @ 14.11.2007 13:51) *

я на бумажке нарисовал smile.gif

Тогда иди на форум художников! lol.gif

Автор: мисс_граффити 14.11.2007 20:20

Вообще-то есть алгоритмы на графах... для поиска оптимального размещения объектов.
Вопрос вот в чем - объект должен находиться в населенном пункте или может на дороге из одного пункта в другой?

Автор: samec 15.11.2007 1:20

Спасибо всем за участие smile.gif Задачку решил. Простым перебором. Хоть и грубое приближение получилось, но и этого хватило smile.gif

Автор: Lapp 15.11.2007 13:06

Цитата(samec @ 14.11.2007 21:20) *
Простым перебором

Прости за любопытство - а перебором по чему? Ты сделал сетку на карте? и перебирал ее узлы? Думаю, это вполне разумный способ..

Автор: Гость 15.11.2007 15:56

Цитата(Lapp @ 15.11.2007 9:06) *

Прости за любопытство - а перебором по чему? Ты сделал сетку на карте? и перебирал ее узлы? Думаю, это вполне разумный способ..

да, именно так и делал smile.gif