بخش ۱۱: گراف

پرسش: یک کلمه شروع، یک کلمه پایان، و یک مجموعه از کلمات که همگی هم طولند داده شده اند. هدف، تبدیل کلمه شروع به کلمه پایان با استفاده از دنباله ای از تغییرات است با این محدودیت که در هر تغییر تنها یک حرف از یک کلمه عوض می شود. کلمات میانی دنباله باید متعلق به لیست مجموعه کلمات داده شده باشند. برنامه ای بنویسید که کوتاهترین دنباله تبدیل برای رسیدن از کلمه شروع به پایان را برگرداند.

پاسخ: طبق معمول کار را با یک مثال آغاز می کنیم تا مطمین شویم که مساله را درست درک کرده ایم. به عنوان مثال اگر کلمه شروع tell و کلمه پایان book باشد و مجموعه کلمات داده شده cool, bell, tool, wool, wage, rage,cook, toll, cage باشند، آنگاه دنباله tell ->toll-> tool-> cool-> cook->book کوتاه ترین دنباله تبدیل می باشد. قبل از اینکه در مورد راه حل این مساله بحث کنیم بگذارید روی یک اصطلاح توافق کنیم: اگر کلمه ای با کلمه ی دیگر تنها در یک حرف متفاوت باشد آنها را ‘مجاور’ هم می نامیم. مثلا toll و tool دو کلمه مجاورند.

اولین الگوریتمی که به آن فکر می کنیم روش جستجوی کامل است. در این روش باید تمام دنباله های کلمات مجاور که رشته شروع را به پایان را می رسانند ایجاد نماییم و در انتها کوچکترین دنباله را به عنوان پاسخ برگردانیم. برای ساخت هر دنباله باید از کلمه شروع آغاز کرد، یک کلمه مجاور از لیست کلمات یافت، و به انتهای دنباله اضافه نمود. در واقع در هر نقطه از یک دنباله باید w (تعداد کل کلمات) را با کلمه کنونی مقایسه کنیم تا بررسی کنیم که آیا مجاور هستند؟ اگر طول کلمات L باشد، حداکثر طول دنباله کلمات L می باشد. با توجه به اینکه هر یک از کلمات مجاور ممکن تا رسیدن به کلمه پایان بکاربرده شوند، پیچیدگی این الگوریتم (O(W^L می باشد که یک تابع نمایی است.

این الگوریتم دو مشکل دارد که آن را اینچنین کند می کنند: (ا) آن که هر مسیر تبدیل را باید تا آخر برویم تا همه مسیرهای ممکن تبدیل را بیابیم، تا اینکه نهایتا بتوانیم کوتاهترین آنها را انتخاب کنیم، و (اا) اینکه هر بار باید همه کلمات را با آخرین کلمه ای که در دنباله تبدیلات به آن رسیده مقایسه کنیم تا کلمات مجاور بعدی در دنباله را انتخاب نماییم. این کار بنظر تکراری می رسد.در ادامه فکر می کنیم که چگونه این مشکلات را حل کنیم.برای واضح تر شدن مشکل این الگوریتم مرتبط با دنبال کردن مسیرهای تبدیل، ساختار مجاورت کلمه ها در مثال بالا را ترسیم کنیم.

نمودار مجاورت کلمات داده شده در ورودی

شکل بالا یک ساختمان داده گراف را تداعی می کند که در آن کلمات گره ها را می سازند و خط بین آنها ارتباط ‘مجاور بودن’ (یعنی تفاوت تنها در یک حرف) دو کلمه را نشان می دهد. الگوریتم جستجوی کامل ارایه شده در واقع این گراف را بصورت عمقی جستجو می کند. در زبان گراف، دلیل اول مطرح شده برای توضیح کند بودن این الگوریتم آن است که باید ابتدا تمام مسیرها را از شروع به پایان پافت و سپس کوتاهترین را تشخیص داد.

خوب، آیا ممکن است که نقطه مقابل روش عمقی جستجوی گراف این مشکل را رفع کند؟ نقطه مقابل جستجوی عمقی، جستجوی سطح به سطح است که این امکان را می دهد در همه مسیرها همزمان و هر بار یک گام پیش برویم. به این ترتیب اولین باری که در یک مسیر به کلمه پایان می رسیم می توانیم مطمین باشیم که کوتاهترین مسیر تبدیل را یافته ایم و نیازی به پیمایش همه مسیر ها تا پایان وجود ندارد. بنابر این استفاده از جستجوی سطح به سطح برای پیمایش گراف مشکل اول الگوریتم را حل خواهد کرد.

ایراد دوم الگوریتم مربوط به مقایسه مجدد کلمه ها با همدیگر برای یافتن مجاورهای یک کلمه است. برای رفع این مشکل می توانیم ابتدا یکبار همه کلمات را با یکدیگر مقایسه نماییم و نتیجه را بصورت گراف فوق ذخیره کنیم.  با استفاده از چنین پیش پردازشی، سریعا می توانیم لیست کلمات مجاور هر کلمه را بدست آوریم.اما برای ساختن چنین گرافی هر کلمه باید با کلمه دیگر مقایسه شود. این یعنی w^2 مقایسه که هزینه هر مقایسه L است. بنابر این هزینه ساختن این گراف (O(L*w^2 می باشد.

این ساختار هزینه های آتی یافتن مجاورها را بشدت کم می کند، اما ممکن است بسیار غیر بهینه باشد. در گراف مثال فوق این ایراد عیان می شود: ممکن است که گراف یک مولفه (زیر گرافی متصل از گره ها) داشته باشد که به هیچ وجه نتوانیم از کلمه شروع به آن ها برسیم. مثلا از کلمه شروع هیچ مسیری به کلمات cage, wage, rage وجود ندارد. بنابر این دلیلی برای لحاظ کردن آنها در ساختن گراف مجاورت وجود ندارد. اما قبل از پیمایش گراف نمی توانیم این را بفهمیم. این شبیه مساله مرغ و تخم مرغ است و یک وابستگی حلقه مانند بین این دو مرحله الگوریتم وجود دارد.برای شکستن مساله مرغ و تخم مرغ باید از روش دیگری برای پیمایش گراف استفاده کنیم. جرقه این ایده جدید بر اساس تعریف مجاورت به ذهن می رسد. کلمه مجاور در دنباله تغییرات را می توان مستقیما با جایگزین کردن یک حرف الفبا از L موقعیت حروف در یک کلمه ایجاد نمود. مثلا کلمات aell، bell, cell، … و غیره با جایگزین کردن حرف اول، و کلمات tall، tbll، tcll ، … با جایگزین کردن در محل دوم کلمه tell ایجاد می شوند.

کلماتی که با این ترتیب ایجاد می شوند مجاور کلمه اول می باشند. بنابر این بجای بررسی بین کلمات داده شده برای یافتن کلمه بعدی، آن ها را خودمان ایجاد می کنیم. با استفاده از این روش درواقع گرافی مانند گراف زیر را ایجاد می کنیم.

نمایی از گراف مفهمومی تولید شده در روش ایجاد کلمات و جستجوی سطح به سطح

مشکل کوچک آن است که همه کلمات ایجاد شده الزاما در مجموعه کلمات داده شده وجود ندارند. برای حل این مشکل قبل از استفاده از یک کلمه ایجاد شده برای توسعه به سطح بعد، ابتدا باید بررسی کنیم که آیا آن در لیست کلمات داده شده می باشد؟ خبر خوب آن است که ساختمان داده مجموعه (set) خیلی سریع می تواند پاسخ دهد که آیا یک کلمه تولید شده در مجموعه کلمات داده شده می باشد. اگر از روش ایجاد کلمات و جستجوی سطح به سطح استفاده نماییم، برای هر کلمه 26*L کلمه مجاور تولید می کنیم. از آنجا که w کلمه داریم، هزینه کل یافتن کوتاه ترین تبدیل حداکثر w*L*26خواهد بود که برای مقادیر بزرگ L و W نسبت به الگوریتم جستجوی کامل عمقی بسیار سریع تر است. الگوریتم جستجوی سطح به سطح که از گراف اتصالات پیش پردازش شده استفاده می کند در بدترین حالت دارای پیچیدگی محاسباتی (O(w*L + W^2 می باشد. قسمت W^2 این فرمول مربوط به محاسبه اولیه اتصالات گراف است.

اینکه روش پیش پردازش و سپس جستجوی سطح به سطح در مقایسه با روش ایجاد کلمات و جستجوی سطح به سطح چگونه عمل می کنند بستگی به پارامترهای واقعی W و L دارد. اگر W خیلی از L بزرگتر باشد، آنگاه الگوریتمی که از پیش پردازش استفاده می کند هزینه سنگینی خواهد داشت.اگر که در یک سیستم لیست کلمات ثابت باشند و هر بار کلمه شروع و پایان جدیدی داده شوند، آنگاه صرف می کند که تنها یکبار گراف مجاورت ها را بسازیم و در بارهای دیگر از آنها استفاده کنیم زیرا هزینه سرشکن آن عملا صفر خواهد بود.

می توانیم این موارد را با مصاحبه کننده در میان بگذاریم و ببینیم کدام الگوریتم برای سناریویی که او می خواهد مفید تر است. در اینجا فرض می کنیم که مصاحبه کننده از الگوریتم ایجاد کلمات و جستجوی سطح به سطح استقبال می کند.

در این صورت این الگوریتم روی یک داده ورودی تست می کنیم که مطمین شویم درست کار می کند. سپس شروع به پیاده سازی الگوریتم می کنیم.

نام مناسب برای تابع با پارامترهای مناسب در نظر می گیریم (خط 1). سپس لیست کلمات داده شده  را به همراه کلمه پایان در یک ساختمان داده مجموعه (set) می ریزیم (خط 2). یک شمارنده گام یا سطحی که در مسیرها تا بحال رسیده ایم در نظر می گیریم (خط 3). سپس لایه صفر را با قرار دادن کلمه شروع در آن می سازیم (خط 4). سپس در یک حلقه تکرار که تا رسیدن به آخرین لایه پیش می رویم (خط 5). یک لیست برای قرار دادن عناصر لیست بعد در نظر می گیریم (خط 6). به ازای هر عنصر در لایه کنونی (خط 7) هر بار آن کلمه را با کلمه پایان مقایسه می کنیم. در صورتی که به کلمه پایان برسیم شماره لایه را به عنوان تعداد مراحل رسیدن به آن برمی گردانیم (خط 8 و 9). در غیر این صورت تمام کلمات ممکن مشتق از این کلمه را می سازیم و چک می کنیم که آیا در لیست کلمات داده شده هستند (خط 11 تا 14). در صورتی که کلمه جدید در لیست کلمات باشد آن را به لایه بعد اضافه می کنیم (خط 15) و از لیست کلمات حذف می کنیم (خط 16) تا از مشاهده تکراری این کلمه در مسیرهای طولانی تر جلوگیری کنیم. هنگامی که تمام کلمات مشتق از لایه کنونی را در لایه جدید گذاشتیم، شمارنده لایه را یک واحد می افزاییم (خط 17) و لایه جدید را به عنوان لایه کنونی در نظر می گیریم (خط 18). اگر تمام لایه ها پیمایش و به کلمه پایان نرسیدیم آنگاه مقدار 1- را به نشان عدم وجود پاسخ بر میگردانیم (خط 19).

def findShortestPath(beginWord, endWord, wordList):
	wordList = set(wordList + [endWord])
	layer_count = 0
	layer = [beginWord]
	while layer:
		new_layer = []
		for w in layer:
			if w == endWord:
				return layer_count
			else:
				for i in range(len(w)):
					for c in "abcdefghijklmnopqrstuvwxyz":
						n_word = "{}{}{}".format(w[:i], c, w[i+1:])
						if n_word in wordList:
							new_layer.append(n_word)
							wordList.remove(n_word)
		layer_count += 1
		layer = new_layer
	return -1

پرسش: یک جدول از حروف و یک کلمه کلیدی داریم. الگوریتمی بنویسید که مشخص کنید آیا کلمه کلیدی در جدول وجود دارد بگونه ای که حروف آن در جدول مجاور باشند. دو حرف مجاورند اگر بالا، راست، پایین، یا سمت چپ یکدیگر باشند. نمی توانیم از یک حرف در یک نقطه از جدول دوبار استفاده کنیم.

پاسخ: برای درک بهتر مساله حل آن را با یک مثال شروع می کنیم. اگر کلمه کلیدی Faces و جدول زیر را داشته باشیم، آنگاه الگوریتم باید مقدار True را برگرداند زیرا می توان کلمه Faces را از کنار هم گذاشتن حروف مجاور جدول (همانطور که با رنگ مشخص شده است) ساخت.

مثالی از جدول کلمات و کلمه ای که با دنبال آن هستیم

ابتدا الگوریتم جستجوی کامل را مطرح می کنیم. برای این پرسش الگوریتم جستجوی کامل شامل ایجاد همه کلمات ممکن متشکل از حروف مجاور را بسازیم. اگر کلمه کلیدی میان کلمات تولید شده باشد آنگاه مقدار True را برمی گردانیم. برای ساختن تمام کلمات متشکل از حروف مجاور در جدول باید از هر نقطه جدول شروع کنیم و به 4 جهت بالا، پایین، راست، و چپ حرکت کنیم. در حرکت به هر سمت به خانه جدیدی از جدول می رسیم. باید حرکت به بالا و پایین، راست و چپ بگونه ای انجام دهیم که به خانه قبلی برنگردیم. این کار را تا زمانی انجام می دهیم که به طول کلمه ایجاد شده معادل طول کلمه کلیدی باشد. پس از ایجاد یک کلمه آن را با کلمه کلیدی مقایسه می کنیم.

این روش را می توانیم با مقایسه تدریجی حروف کلمه ایجاد شده با کلمه کلیدی تسریع کنیم. با این صورت که خانه اول را با حرف اول کلمه کلیدی مقایسه می کنیم. چنانچه برابر نبودند عمل ایجاد کلمات از آن خانه را ادامه نمی دهیم. بنظر می رسد که راه حلی جز پیمایش کل ماتریس به این روش نداریم. اما چیزی که این بین کمک می کند راه حل را بهتر درک کنیم در نظر گرفتن مشابهت ارتباط بین خانه های جدول و یک گراف است. در واقع هر خانه جدول یک گره در گراف است و به گره هایی که در سمت راست، چپ، بالا، و پایین آن هستند متصل می شوند.


بنابر این الگوریتم تعریف شده در واقع یک جستجوی عمقی در گراف از هر گره آن می باشد. برای پیاده سازی نیاز به ساختن گره ها و اتصالات آنها به روش مرسوم ساخت گراف نداریم. شماره سطر ستون یک خانه از جدول برای یافتن گره هایی که در گراف همسایه هستند استفاده می شوند.بنابر این شروع به پیاده سازی برنامه می کنیم. ابتدا نام تابع و پارامترهای مناسب را تعریف می کنیم (خط 1). سپس تعداد سطر و ستون جدول را در متغیر هایی می گذاریم که بعدا بتوانیم راحت از آنها استفاده کنیم (خط 2 و 3). به دلیل مشابه طول کلمه کلیدی را در متغیری می گذاریم (خط 4). سپس یک ماتریس به عنوان سایه ماتریس اصلی با مقادیر اولیه False برای همه خانه های می سازیم (خط 5 و 6). در ادامه پیاده سازی با تغییر مقدار خانه های این جدول به True از استفاده مجدد یک حرف در ایجاد یک کلمه جلوگیری می کنیم. برای فرمول کردن حرکت به راست، چپ، بالا، و پایین از یک لیست از لیست ها استفاده می کنیم (خط 7). هر عنصر لیست دارای دو عنصر است که اولین عنصر میزان حرکت در سطر و دومی در ستون را برای رسیدن به عنصر مجاور مناسب نشان می دهد. تابع داخلی dfs در واقع از خانه (i , j)جدول شروع به یافتن ادامه کلمه کلیدی (از اندیس seq به بعد) می کند (خط 9). قبل از تشریح داخل این تابع سراغ مابقی سطرهای برنامه می کنیم. خط 25 تا 28 در دو حلقه تکرار تو در تو ماتریس را می پیماید و امتحان می کند که آیا می توان کلمه کلیدی را از یک خانه ماتریس ساخت. برای تشخیص این امر هر بار تابع داخلی را فراخوانی می کند (خط 27). حال به تشریح تابع داخلی ادامه می دهیم. این یک تابع بازگشتی است و خود را فراخوانی می کند تا جایی که با انتهای کلمه کلیدی نرسیده ایم و همچنان حروف جدول در مسیر پیموده شده با حروف کلمه کلیدی برابرند. به این دلیل هر بار حرف در موقعیت (i, j)ماتریس را با عنصر موقعیت seq در کلمه کلیدی مقایسه می کنیم. در صورتی که برابر نباشند این مسیر را ادامه نمی دهیم (خط 22 و 23). در صورتی که برابر باشند و این آخرین حرف در کلمه کلیدی باشد با این معناست که کلمه کلیدی در جدول موجود است (خط 11 و 12). اگر به انتهای کلمه کلیدی نرسیده باشیم باید این خانه (i, j) را نشان گذاری کنیم تا در ادامه مسیر کنونی از آن دوباره استفاده نکنیم (خط 13). سپس برای هر یک از جهت های حرکت در یک حلقه تکرار (خط 14) اندیس موقعیت های بعدی را می سازیم (خط 15 و 16). آنگاه بررسی می کنیم که اندیس ها خارج از ماتریس نیفتاده باشند و همچنین خانه مورد نظر قبلا در این مسیر استفاده نشده باشد (خط 17 و 18). در صورت امکان حرکت به نقطه جدید تابع را بصورت بازگشتی فراخوانی می کنیم (خط 19). در صورتی که حاصل جستجو موفقیت آمیز باشد به جستجو خاتمه می دهیم (خط 20). در صورتی که جستجو موفقیت آمیز نبود نشان خانه (i, j) را به false تنظیم می کنیم تا مسیر بعدی بتواند برای تشکیل کلمات از آن استفاده نماید (خط 22).

def find(board, word):
	row_len  = len(board)
	col_len  = len(board[0])
	word_len = len(word)
	checked    = [[False for _ in range(col_len)] for _ in range(row_len)]

	directions = [[0,1], [0, -1], [-1, 0], [1, 0]]

    def dfs(i, j, seq):
		if board[i][j] == word[seq]:
			if seq+1 == word_len:
				return True
			checked[i][j] = True
			for d in directions:
				ni = i+d[0]
				nj = j+d[1]
				if 0<=ni<row_len and  0<=nj<col_len and (not checked[ni][nj]):
					
					if dfs(ni, nj, seq+1):
						return True
			
			checked[i][j] = False
			return False

	for i in range(row_len):
		for j in range(col_len):
			if dfs(i, j, 0):
				return True
	return False





GiottoPress by Enrique Chavez