Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

§5. Алгебраический метод построения гамильтоновых циклов 15

§6. Метод перебора Робертса и Флореса 16

§8. Улучшение метода Робертса и Флореса 18

§9. Мультицепной метод 19

§10. Сравнение методов поиска гамильтоновых циклов 21

Глава 3. Задача коммивояжера 23

§1. Общее описание 23

§2. “Жадный” алгоритм решения ЗК 25

§3. “Деревянный” алгоритм решения ЗК 26

§4. Метод лексикографического перебора 28

§5. Метод ветвей и границ решения ЗК 29

§6. Применение алгоритма Дейкстры к решению ЗК 34

§7. Метод выпуклого многоугольника для решения ЗК 34

§8. Генетические алгоритмы 36

§9. Применение генетических алгоритмов 39

Список литературы 41

Введение

Целью моей курсовой работы является описание методов нахождения и построения эйлеровых и всех гамильтоновых циклов в графах, а также сравнительный анализ этих методов. Другая цель решаемая в данной работе — это рассмотрение задачи коммивояжера и методов ее решения (включая эвристические и генетические алгоритмы).

Прежде всего, чтобы внести ясность и уточнить терминологию, хотелось бы дать определения некоторым элементам графа таким, как маршрут, цепь, цикл.

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер: v0,e1, … en,vn, в которой любые два соседних элемента инцидентны. Если v0 = vn, то маршрут замкнут, иначе открыт.

Если все ребра различны, то маршрут называется цепью. Если все вершины
(а значит, ребра) различны, то маршрут называется простой цепью.

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом. Граф без циклов называется ациклическим. Для орграфов цепь называется путем, а цикл — контуром.

Глава 1. Эйлеровы циклы

Требуется найти цикл, проходящий по каждой дуге ровно один раз. Эту задачу впервые поставил и решил Леонард Эйлер, чем и заложил основы теории графов, а соответствующие циклы теперь называются эйлеровыми. Фигуры, которые требуется обрисовать, не прерывая и не повторяя линии, также относятся к эйлеровым циклам.

Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протекающая через
Калининград (прежде город назывался Кенигсбергом), омывает два острова.
Берега реки связаны с островами так, как это показано на рисунке.

Рекомендуем скачать другие рефераты по теме: доклад на тему культура, реферат н.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата