Search

In this study, we consider the multiple traveling salesmen problem (mTSP) with the min-max objective of minimizing the longest tour length. We begin by reviewing an existing integer programming (IP) formulation of this problem. Then, we present several novel conjunctive normal form (CNF) encodings and an approach based on modifying a maximum satisfiability (MaxSAT) algorithm for the min-max mTSP. The correctness and the space complexity of each encoding are analyzed. In our experiments, we compare the performance of solving the TSP benchmark instances using an existing encoding and our new encodings comparing the results achieved using an implemented group MaxSAT solver to those achieved using the IP method. The results show that for the same problem, the new encodings significantly reduce the number of generated clauses over the existing CNF encoding. Although the proposals are still not competitive compared to the IP method, one of them may be more effective on relatively large-scale problems, and it has an advantage over the IP method in solving an instance with a small ratio of the number of cities to the number of salesmen.

Mobile stereo matching systems are becoming more important in many applications such as auto-driving and autonomous robots. However, to maintain its low power consumption, mobile platforms have only limited hardware resources. Accurate stereo matching methods require a high computational complexity, and it is difficult to maintain both acceptable accuracy and processing speed on the mobile platforms. To solve this trade-off, in this paper, we propose a novel acceleration approach for a well-known matching algorithm Zero-means Normalized Cross Correlation (ZNCC), and show its effectiveness on a Jetson TX2 embedded GPU. By combining our new approach, Z2- ZNCC, with the Semi-Global Matching (SGM) algorithm, our system achieves a low error rate of 7.76% while keeping 28 fps for 1242×375 pixels images with the maximum disparity of 128 on the KITTI 2015 dataset. This performance is higher than previous state-of-the-art system on the same hardware platform.

Mafia, a game with high logic, is very popular around the world. Players from all over the world constantly alter the rules of the game to increase the complexity and the entertainment of the game. With increasing the character and number of participants, the balance between the citizens and Mafias is more difficult to maintain. Although little study has been done on Mafia Game, there are some studies which indicate to us the criteria and methods to maintain balance. Among them, there are two main theories: 1) Some studies present the best ratio of the number of Citizens and Mafias, from the perspective of the winning-chance, and use a mathematical model to prove the correctness of the ratio for simple version. 2) Some studies focus on selecting the best ratio from the perspective of the entertainment by analyzing the overall death toll based on the Game Refinement Theory. Although the two above theories have different perspectives and their conclusions are not absolute, both of them are necessary for players. However, most of the studies only do their evaluation according to the theories of themselves, and few studies combine the two theories together to analysis the balance of the Mafia Game between the different characters. In this paper, we proposed simulator which can simulate the various of actions more realistically in Mafia Game. Different from other simulators, it adds a weight of credibility to each character, which can change continuously as the game progresses, and make it more clearly to distinguish the identity of each player. Additionally, the simulation results are analyzed according to the above two theories, which helps us to understand the relationship between the them, and to find a best combination solution dynamically as the change of the total number of players.