مسئله فروشنده دوره‌گرد
Travelling Salesman Problemمسئله فروشنده دوره‌گرد یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
اول این مفهوم را در ذهن نگه دار
مسئله فروشنده دوره‌گرد یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم مسئله فروشنده دوره‌گرد ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
مشخص کن گراف directed/undirected و weighted/unweighted است.
representation گراف را انتخاب کن.
state الگوریتم و حالت disconnected/cycle را صریح مدیریت کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای مسئله فروشنده دوره‌گرد هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- فقط وقتی assumptionهای الگوریتم با مسئله گراف هماهنگ است از آن استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- فراموش کردن componentهای disconnected.
- قاطی کردن shortest path وزن‌دار و بدون وزن.
- مدیریت نکردن revisit/cycle.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای مسئله فروشنده دوره‌گرد در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
مسئله فروشنده دوره‌گرد چه مسئله‌ای را حل می‌کند؟
مسئله فروشنده دوره‌گرد یک الگوریتم از دسته گراف‌ها است. این الگوریتم روی Nodeها و Edgeهای گراف کار می‌کند و معمولاً به representation مثل adjacency list/matrix و stateهایی مثل visited، distance، parent یا indegree نیاز دارد.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
فراموش کردن componentهای disconnected.