Разработать приложение для поиска путей в графе с интерфейсом к БД

40 000 руб. за проект • наличный расчёт, безналичный расчёт
14 января 2019, 15:22 • 6 откликов • 114 просмотров
Краткое описание проекта:
Разработать приложение для поиска путей в графе с интерфейсом к БД.

Непосредственно описание задачи:
Необходимо написать консольное приложение-сервер на С++, компилируемом GNU C Compiler Suite, (альтернативы обсуждаемы) для поиска путей в графе.

Рёбра графа представлены путями, сохранёнными в БД PostgreSQL в виде:

1. Пункт отправления.
2. Дата отправления.
3. Время отправления.
4. Пункт прибытия.
5. Дата прибытия.
6. Время прибытия.
7. Продолжительность маршрута.
8. Количество пересадок, описываемых данным маршрутом.
9. Цифровой идентификатор перевозчика.

Необходимо найти все маршруты из точки А (опционально посещая все точки из списка Вх) в Б через граф, удовлетворяющие заданным фильтрам:

1. Количество пунктов пересадки. (без пересадок, максимум N пересадок, любое количество пересадок).
2. Максимальная продолжительность путешествия минут (например, 1440).
3. Список перевозчиков (белый, чёрный).
4. Список промежуточных пунктов (белый, чёрный).
5. Ночёвка в промежуточных пунктах (только, только не).
6. Минимальное время пересадки в промежуточных пунктах.
7. Динамическое время пересадки, возвращаемое функцией от входящего и исходящего ребра.
8. Отправление С, ДО, в промежутке.
9. Прибытие С, ДО, в промежутке.
10. Посещение точек в списке Вх в любой последовательности (задача коммивояжёра). Приналичии Вх точка Б может равняться А.

Задача подразумевает несколько этапов выполнения:

Этап 1 (15%):
Разработка поиска в графе без функционала коммивояжёра, без интерфейса к БД, без использования фильтров.

Этап 2 (15%):
Внедрение использования фильтров, без коммивояжёра.

Этап 3 (20%):
Внедрение интерфейса к БД. (Начальное чтение рёбер из БД, получение задач из БД LISTEN/NOTIFY/SELECT FOR UPDATE/UPDATE). После прочтения рёбер из БД данные сохраняются в памяти приложения.

Этап 4 (10%):
Разработка мультизадачности (multithreading, conсurrent execution).

Этап 5 (15%):
Внедрение функционала коммивояжёра.

Этап 6 (25%):
Доработка функционала в соответствии с требованиями, которые не были учтены в проекте изначально. Время, затраченное на данный этап, не может превышать более 25% от всего проекта. Если доработки не требуются, оплата данного этапа будет произведена сразу после проверки кода из этапа 5. В случае, если на разработку дополнительного функционала требуется больше времени, разработка останавливается по достижении 100% запланированного времени, заказчик оплачивает этап и код передаётся заказчику "как есть".

Дата начала работы:
По договоренности.

Дата сдачи работы:
На выполнение проекта запланировано около четырёх недель.

Необходимость промежуточной оценки результата:
Проект поделён на этапы. Работоспособность каждого этапа должна быть продемонстрирована по скайпу.

Количество доработок, включенных в стоимость заказа:
(для случаев, когда приложение работает в соответствии с требованиями проекта)
Этапы с 1-го по 5-ый подразумевают одну бесплатную доработку длиной не более часа.
Также см. этап 6.

Варианты оплаты работы:
Предпочтительный вариант оплаты - по безналу переводом на карту или банковский счёт. Наличный расчёт – исключение, о котором необходимо договариваться заранее. Оплата производится по факту выполнения этапов, либо, по желанию, одной суммой за весь проект целиком.

Дополнительные условия:
Исполнитель ответственен за уплату всех полагающихся налогов и сборов.

Кодовая фраза:
1. Начните отклик с описания алгоритма поиска в графе, который Вы бы использовали в этой задаче. Объясните (!), почему именно этот, а не другие.
2. После этого расскажите, на каком языке вы планируете разрабатывать задачу. Объясните, почему именно на нём, а не на других.
Файлы