Помощь - Поиск - Пользователи - Календарь
Полная версия: Нахождение кратчайшего пути
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
samec
Условие:
----------------------------------------------------------
Для снабжения населенных пунктов, расположенных в труднодоступной местности, требуется разместить жд станцию и аэродром таким образом, чтобы суммарное расстояние воздушных перевохок от станции к аэродрому и от аэродрома к населенным пунктам было минимальным.
Координаты населенных пунктов:
Код
Номер пункта    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
Я правильно понял, что товары привозят по ЖД, потом от станции воздухом до АП, а потом ножками до каждого НП?
Табличка не совсем понятная.. Так, что ли:

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

- да?
И нужно минимизировать сумму всех маршрутов?
samec
Да, всё верно, только от аэродрома до населенных пунктом тоже вертолёт летать будет. Таблички подправил.
Да. нужно минимизаровать сумму всех маршрутов.
Lapp
Ну, я бы начал с того, что нарисовал это все. Оно, может, и не совсем правильно - зато хоть как-то оживит процесс. Тем более, что графика все равно нужна smile.gif.
Выбираешь масштаб, наносишь все объекты, подписываешь.. А там видно будет smile.gif))
samec
я на бумажке нарисовал smile.gif
Lapp
Цитата(samec @ 14.11.2007 13:51) *

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

Тогда иди на форум художников! lol.gif
мисс_граффити
Вообще-то есть алгоритмы на графах... для поиска оптимального размещения объектов.
Вопрос вот в чем - объект должен находиться в населенном пункте или может на дороге из одного пункта в другой?
samec
Спасибо всем за участие smile.gif Задачку решил. Простым перебором. Хоть и грубое приближение получилось, но и этого хватило smile.gif
Lapp
Цитата(samec @ 14.11.2007 21:20) *
Простым перебором

Прости за любопытство - а перебором по чему? Ты сделал сетку на карте? и перебирал ее узлы? Думаю, это вполне разумный способ..
Гость
Цитата(Lapp @ 15.11.2007 9:06) *

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

да, именно так и делал smile.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.