ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Молодые люди, задача коммивояжера для вас не сложна?
25 сообщений из 33, страница 1 из 2
  1  все
Молодые люди, задача коммивояжера для вас не сложна?
    #32116904
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
Очень нужна ваша помощь!
Помогите мне в написании на Паскале программы коммивояжера.
нужен исчерпывающий алгоритм.
Задача заключается в нахождении в торговом участке коммивояжера тура из N городов с наименьшей стоимостью. Каждый город входит в тур только один раз
...
Рейтинг: 0 / 0
10.03.2003, 12:51
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32116942
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
Мы совсем не молодые, не совсем люди, и еще мы ленивы. Короче, качаем тут .
...
Рейтинг: 0 / 0
10.03.2003, 14:31
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32117068
StarWind
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
StarWind
Участник
как это все похоже на лабораторную работу, которую не хочет делать ленивая студентка... ))
...
Рейтинг: 0 / 0
11.03.2003, 04:14
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32118408
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
Знаете ли, не молодые, этот алгоритм мне совсем не нужен, с текстовыми файлами.

мне нужно вот что

реализовать исчерпывающим и эвристическим методом

Необходимо рассмотреть все возможные варианты проезда, посчитать стоимость каждого и выбрать тур с мин. стоимостью. Задача сводится к генерации всех перестановок заданного множества внутренних городов (рекурсия).

Шаг 0. Инициализация данных (установка в начальное положение)
SetTour =0, mincost =∞;
Шаг 1. Цикл по всем перестановкам
For I :=1 to(n-1)! do шаг 4
Шаг 2 Получение новой перестановки
Set P:=I-ая перестановка целых чисел 1,2,…, n-1. (здесь нужен подалгоритм).
Шаг 3 Построение нового тура Т(р), соответствующий перестановке Р.
и вычисление стоимости Cost(T(p)) ( здесь нужно 2 подалгоритма)
Шаг 4 Сравнение
If Cost(T(p))<mincost then SetTour:=T(p) ;
Mincost:= Cost(T(p)).


В эвристическом методе,
коммивояжер выбирает из всех, путь с самой низкой стоимостью, заранее не зная, какой путь будет следующим.
Шаг 0: инициализация SetTour =0, mincost =0; V=U;
Помечаем U –«использована», а все другие вершины «не использованы» (вершина V – положение на сети в данный момент)
Шаг 1: посещение всех городов
For k:=1 to n-1 do шаг2
Шаг 2: выбор следующего ребра. Пусть(V,W) – ребро с наименьшей стоимостью, ведущее из V в любую неиспользованную вершину W;
SetTour:= Tour+(V,W);

Спасибо
...
Рейтинг: 0 / 0
12.03.2003, 15:13
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32118462
Фотография Циничный Кот
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Циничный Кот
Участник
Чего-то я конкретно не догнал. А в чем вопрос-то???
...
Рейтинг: 0 / 0
12.03.2003, 15:41
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32118542
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
На паскале НУЖНО 2 программы! ВОТ!
Догнал?
...
Рейтинг: 0 / 0
12.03.2003, 16:40
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32118550
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
2Ангелина

Молодая-интересная, можно Вас попросить не отвлекать ЦК от важных дел (ему еще пиво пить и про кружочки объяснять). Учитесь думать своей головой , пожалуйства.

Извините, если был груб :)
...
Рейтинг: 0 / 0
12.03.2003, 16:45
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32118850
StarWind
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
StarWind
Участник
Ангелина, ну раз вы так ловко рисуете алгоритмы, то думаю с такой простенькой работой как кодер влет справитесь
...
Рейтинг: 0 / 0
13.03.2003, 03:51
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119153
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
Огромное спасибо, больше я вас не отвлекаю
...
Рейтинг: 0 / 0
13.03.2003, 12:15
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119194
Фотография Циничный Кот
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Циничный Кот
Участник
Программы??? Нужно???... Нуу, этто вы ваще... Это - задача непростая, так с ходу не делается... Особенно без пива - оно как масло в двигателе.... :о) Вроде мелочь, а без него нифига не работает... Так что мой вам совет - купите ящик пива, поставьте его кому надо, глядишь, чудо и произойдет - проги сами собой появятся...
...
Рейтинг: 0 / 0
13.03.2003, 12:39
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119581
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
Как жаль, что вы, вероятно, живёте не в моём городе
...
Рейтинг: 0 / 0
13.03.2003, 17:27
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119607
Фотография Циничный Кот
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Циничный Кот
Участник
Жаль, ага... Но зато как хорошо, что любители пива живут не только в моем городе...
...
Рейтинг: 0 / 0
13.03.2003, 17:43
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119933
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
2NNN
как на своих клонов так ты не рычишь
а тут на тебе
...
Рейтинг: 0 / 0
14.03.2003, 10:39
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119935
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tchingizПривилегированный пользователь
Участник
и задача почти про тебя была - проехать N городов
...
Рейтинг: 0 / 0
14.03.2003, 10:40
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32119945
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
2tchingiz

Ну, во-первых, на моих клонов рычать бесполезно в силу их непробиваемой тупости. Во-вторых, никто и не рычал, я просто пытался стимулировать человека на самостоятельные действия. В-третьих, я на всякий случай извинился.
...
Рейтинг: 0 / 0
14.03.2003, 10:59
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120059
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
Стимулировать, это спасибо, но было бы полезнее если бы кто-нибудь
помогал шаг за шагом, мне же надо с кем-то советоваться.
...
Рейтинг: 0 / 0
14.03.2003, 12:46
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120076
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
2Ангелина

Дык мы разве отказываемся? Сейчас какой шаг актуален?
...
Рейтинг: 0 / 0
14.03.2003, 12:55
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120088
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
eNose
Участник
[не активирован]
[не одобрен]
Ангелина, задача этого самого коммивояжера конечно же не сложна.
Вернее, БЫЛА НЕ СЛОЖНА лет несколько назад, когда я учился в ВУЗе...

Но, если мне не изменяет память, она относится к классы т.н. NP- полных задач... То есть, начиная с некоторого N, Вы замучаетесь ждать окончания работы алгоритма. Вам точно нужно решение полным перебором? Или нужен алгоритм поиска решения, приближенного к оптимальному?
...
Рейтинг: 0 / 0
14.03.2003, 13:01
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120142
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
мне нужен исчерпывающий алгоритм, для начала.
рекурсия. именно полный перебор.
...
Рейтинг: 0 / 0
14.03.2003, 13:58
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120576
Фотография чингиз
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
чингиз
Участник
NNN>Ну, во-первых, на моих клонов
NNN>рычать бесполезно в силу их непробиваемой тупости

гы главное - оригинал хороший и умный.
а может статься что Ангелине нафиг алгоритм (назвается ветвей и границ кстати - небольшое улучшиние прямого перебора) не надо.
может она хочет пиво просто попить.
прямо скажешь набежит куча облезлых кошаков и будут обзываться.
вот человек и мучается.
...
Рейтинг: 0 / 0
14.03.2003, 22:44
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120607
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
2чингиз

> гы главное - оригинал хороший и умный.

Ну я бы не стал так говорить

> а может статься что Ангелине нафиг алгоритм (назвается ветвей и границ кстати - небольшое улучшиние прямого перебора) не надо. может она хочет пиво просто попить. прямо скажешь набежит куча облезлых кошаков и будут обзываться. вот человек и мучается.

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

2Ангелина

Я все равно до сих пор не понял, что там с шагом 0. Как происходит инициализация? В функцию передается массив, содержащий цены на билеты между каждым пунктом? Количество N заранее известно? Даже не представляю, поддерживает ли паскаль массивы переменной размерности и передачу массивов в качестве аргументов.
...
Рейтинг: 0 / 0
15.03.2003, 09:02
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120705
ангелина
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ангелина
Участник
другое. пока :))
N- заранее известно, предположим будет 5 городов. Нужно преребрать все варианты(генерация всех перестановок) дорог, и найти путь самый дешёвый, начиная с 1Извините, NNN, если я вас немного ещё поспрашиваю.
Пива попить это конечно неплохо.
Заботит города . далее 2,3,4,5, и возвращаясь опять в 1-ый.
Как сделать генерацию всех перестановок, при этом находить суммму каждого пути? как это мне организовать? Ещё. Как задать цены всех дорог? в отдельном массиве?
...
Рейтинг: 0 / 0
15.03.2003, 22:52
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120710
c127
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
c127
Гость
Вот тебе генерация всех перестановок:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

void AllP(unsigned iCurr, unsigned *pP);
void printt(unsigned *p);

unsigned iSize;

/***************************** AllP *********************/
void AllP(unsigned iCurr, unsigned *Pp)
{
int j = iSize;
int i;
unsigned *p;

if (iCurr>iSize){
printt(Pp);
return;
}
p = (unsigned *)malloc((iSize+1)*sizeof(int));
while (j>=1) p[j] = Pp[j--];
AllP(iCurr+1,p);
for (i=iCurr; i>1; i--){
p = p[i-1];
p[i-1] = iCurr;
AllP(iCurr+1,p);
}
free(p);
}
/********************* printt ***************************/
void printt(unsigned *p)
{
int j;
printf("\n");
for (j=1; j<=iSize; j++) printf("%1u,",p[j]);
printf("\n");
}

инициализация, деинициализация, вызов:
iSize=(unsigned) 3141508050623;
ipP = (unsigned *)malloc((iSize+1)*sizeof(int));
for (j=1; j<=iSize; j++) ipP[j] = j;
AllP(2,ipP);
free(ipP);
...
Рейтинг: 0 / 0
16.03.2003, 02:32
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120721
Фотография чингиз
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
чингиз
Участник
NNN>Ну я бы не стал так говорить
ну еще и скромный
а хочешь знать правду - спроси кошкинсона или аха
...
Рейтинг: 0 / 0
16.03.2003, 09:26
| Ответить | Цитировать | Написать  
Молодые люди, задача коммивояжера для вас не сложна?
    #32120766
Фотография NNN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NNN
Участник
2Ангелина

> Заботит города . далее 2,3,4,5, и возвращаясь опять в 1-ый.
Как сделать генерацию всех перестановок, при этом находить суммму каждого пути? как это мне организовать? Ещё. Как задать цены всех дорог? в отдельном массиве?

Надо определиться с исходной перестановкой [2,3,4,5] и получить все варианты их будет, 24 ((N-1)!). Вот тут примерчик на сях кинули, может кто на паскаль переведет. Затем получить все суммы для комбинаций, выбрать из них минимальную и запомнить номер. Данные, имхо, удобнее хранить в таком виде
Array Prices[1..N,1..N] as real // стоимость билетов
Array Pathes[1..(N-1)!,1..N+1] as real // все возможные пути, причем Pathes[X,1]=1 и Pathes[X,N+1]=1, первый и конечный пункт нам известны
Array Summas[1..(N-1)!] as real // все возможные суммы
Ввести суммы можно так (если считать, что стоимость билета из пункта 1 в пункт 2 равна стоимости билета в противоположном направлении)
for i:=1 to N do
for j:=1 to N do
if i<j then
Price[i, j]=input...
Price[j, i]=Price[i, j]
end;
end;
end;
Главное найти переставки, а мне что-то нормальный мануал по этой теме не попадается..

> Пива попить это конечно неплохо.

До пятницы - трезвость - норма жизни.

2чингиз

> ну еще и скромный

А ты только узнал? Моя скромность незнает границ, я всегда об этом говорил :)

> а хочешь знать правду - спроси кошкинсона или аха

Если тебе интересно - спроси сам. А мне это вроде как ни к чему..
...
Рейтинг: 0 / 0
16.03.2003, 15:43
| Ответить | Цитировать | Написать  
25 сообщений из 33, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Молодые люди, задача коммивояжера для вас не сложна?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]