BibTex RIS Cite

A PARALLEL DEPTH-FIRST SEARCH ALGORITHM USING LIST OF QUEUES ON PEG SOLITAIRE GAME

Year 2014, Volume: 15 Issue: 1, 69 - 80, 05.05.2015
https://doi.org/10.18038/btd-a.04907

Abstract

For the Peg Solitaire game, existing computers can easily compute the moves required to obtain the solution board with one peg in a short time by applying the DFS algorithm. In order to shorten the solution time, advantages of parallel processing has been used in this paper. The problems that occur during locking and unlocking while accessing shared resources and processing sibling nodes before child nodes are solved by introducing List of Queues data structure and shorter execution times has been obtained compared to non-parallel DFS solution. English version of the Peg Solitaire game has been used in the experiments

References

  • Beasley, J. D. (1985). The Ins and Outs of Peg Solitaire. AMC, 10, 12.
  • Kendall, G., Parkes, A. J., & Spoerer, K. (2008).
  • A Survey of NP-Complete Puzzles. ICGA Journal, 31(1), 13-34. Kiyomi, M., & Matsui, T. (2001). Integer
  • Programming Based Algorithms for Peg Solitaire Problems. In Computers and Games ( Heidelberg. Springer Berlin Matos, A. (1998). Depth-Şrst Search Solves Peg
  • Solitaire. Technical Report DCC-98-10, Universidade do Porto. Available from http://www.dcc.fc.up.pt/Pubs/treports.htm l, last accessed 16 July 2014.
  • Moore, C. and Eppstein, D. (2002). One
  • Dimensional Peg Solitaire, and Duotaire. More Games of No Chance (ed. R. Nowakowski), number 42, 341–350. Cambridge University Press, New York, NY. Peg Solitaire. http://en.wikipedia.org/wiki/Peg_solitaire [last accessed 16 July 2014].
  • Rao, V. N., & Kumar, V. (1987). Parallel Depth First
  • Implementation. International Journal of Parallel Programming, 16(6), 479-499. I. Ravikumar, B. (2004). Peg-solitaire, String Systems Rewriting
  • Automata. Theoretical Science, 321(2), 383-394. and Finite Computer Saad, R. T., Dal Zilio, S., & Berthomieu, B. (2012). An Experiment on Parallel Model Checking
  • In Automated Technology for Verification and Analysis ( 284-299). Springer Berlin Heidelberg. CTL Fragment. Uehara, R., & Iwata, S. (1990). Generalized Hi- Q TRANSACTIONS 270-2 (1976-1990), 73(2),

SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI

Year 2014, Volume: 15 Issue: 1, 69 - 80, 05.05.2015
https://doi.org/10.18038/btd-a.04907

Abstract

Solo Test oyununda tablada tek taşın kaldığı duruma ulaşmak için takip edilmesi gereken hamleler, DFS algoritmasıyla günümüz bilgisayarlarında kısa sürede bulunabilmektedir. Bu sürenin kısaltılması amacıyla bu makalede paralel işlemenin avantajları kullanılmaya çalışılmıştır. Paralel DFS algoritmalarında karşılaşılan, ortak kaynaklara erişimde kullanılan kilitlerin kapatılıp açılması ve bir düğümün çocuklarının işlenmeden kardeşlerinin işlenmesi durumlarında ortaya çıkan problemler, Kuyruk Listesi adı verilen veri yapısının kullanımı ile aşılmaya çalışılmıştır ve paralel olmayan DFS çözümüne oranla daha kısa sürelerde çözüme ulaşılmıştır. Deneylerde Solo Test oyununun İngiliz versiyonu kullanılmıştır

References

  • Beasley, J. D. (1985). The Ins and Outs of Peg Solitaire. AMC, 10, 12.
  • Kendall, G., Parkes, A. J., & Spoerer, K. (2008).
  • A Survey of NP-Complete Puzzles. ICGA Journal, 31(1), 13-34. Kiyomi, M., & Matsui, T. (2001). Integer
  • Programming Based Algorithms for Peg Solitaire Problems. In Computers and Games ( Heidelberg. Springer Berlin Matos, A. (1998). Depth-Şrst Search Solves Peg
  • Solitaire. Technical Report DCC-98-10, Universidade do Porto. Available from http://www.dcc.fc.up.pt/Pubs/treports.htm l, last accessed 16 July 2014.
  • Moore, C. and Eppstein, D. (2002). One
  • Dimensional Peg Solitaire, and Duotaire. More Games of No Chance (ed. R. Nowakowski), number 42, 341–350. Cambridge University Press, New York, NY. Peg Solitaire. http://en.wikipedia.org/wiki/Peg_solitaire [last accessed 16 July 2014].
  • Rao, V. N., & Kumar, V. (1987). Parallel Depth First
  • Implementation. International Journal of Parallel Programming, 16(6), 479-499. I. Ravikumar, B. (2004). Peg-solitaire, String Systems Rewriting
  • Automata. Theoretical Science, 321(2), 383-394. and Finite Computer Saad, R. T., Dal Zilio, S., & Berthomieu, B. (2012). An Experiment on Parallel Model Checking
  • In Automated Technology for Verification and Analysis ( 284-299). Springer Berlin Heidelberg. CTL Fragment. Uehara, R., & Iwata, S. (1990). Generalized Hi- Q TRANSACTIONS 270-2 (1976-1990), 73(2),
There are 11 citations in total.

Details

Primary Language Turkish
Journal Section Articles
Authors

Muzaffer Doğan

Publication Date May 5, 2015
Published in Issue Year 2014 Volume: 15 Issue: 1

Cite

APA Doğan, M. (2015). SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering, 15(1), 69-80. https://doi.org/10.18038/btd-a.04907
AMA Doğan M. SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI. AUJST-A. May 2015;15(1):69-80. doi:10.18038/btd-a.04907
Chicago Doğan, Muzaffer. “SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 15, no. 1 (May 2015): 69-80. https://doi.org/10.18038/btd-a.04907.
EndNote Doğan M (May 1, 2015) SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 15 1 69–80.
IEEE M. Doğan, “SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI”, AUJST-A, vol. 15, no. 1, pp. 69–80, 2015, doi: 10.18038/btd-a.04907.
ISNAD Doğan, Muzaffer. “SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 15/1 (May 2015), 69-80. https://doi.org/10.18038/btd-a.04907.
JAMA Doğan M. SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI. AUJST-A. 2015;15:69–80.
MLA Doğan, Muzaffer. “SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI”. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering, vol. 15, no. 1, 2015, pp. 69-80, doi:10.18038/btd-a.04907.
Vancouver Doğan M. SOLO TEST OYUNU ÜZERİNDE KUYRUK LİSTESİ İLE BİR PARALEL ÖNCE-DERİNE ARAMA ALGORİTMASI. AUJST-A. 2015;15(1):69-80.